package com.cuz.daileetcode.utils;


import java.util.*;
import java.util.stream.Collectors;

/**
 * @author cuzz
 * @version 1.0
 * @description: 滑动窗口
 * @date 22:04 2021/12/29
 **/
public class SlideWindow<T> {

    /****
     * 双端队列缓存数据对于下表
     */
    private Deque<Integer> doubleQueue;
    /***
     * 将copy 原数据 集合数据 or 数组数据
     * 缓存在此 使用ArrayList实现 保证根据下标索引数据时间复杂度为常数
     */
    private List<T> sourceDataMemory;
    /**
     * 滑动窗口的左边界
     */
    private int lIndex;
    /**
     * 滑动窗口的右边界
     */
    private int rIndex;
    /**
     * 比较器 可以传入可以比较的对象 or传入比较器
     * 如果比较器不为null 那么优先使用比较器
     */
    private Comparator<T> comparator;

    private SlideWindow() {
    }

    /***
     * 深拷贝 sourceDate
     * 为什么深拷贝，防止后续滑动窗口使用中，用户更改sourceDate
     * 让滑动窗口的无法准确返回最极端的值
     *
     * @param sourceDate 集合
     * @param <T> 无任何限制
     * @return SlideWindow 实例
     */
    public static <T> SlideWindow<T> create(Collection<T> sourceDate) {
        //实例
        SlideWindow<T> resSw = new SlideWindow<>();
        //转换为数组
        T[] objects = (T[]) Objects.requireNonNull(sourceDate).toArray();
        //深拷贝
        T[] copyRes = Arrays.copyOf(objects, sourceDate.size());
        //转换为list stream collect(Collectors.toList()) 默认返回arrayList
        resSw.sourceDataMemory = Arrays.stream(copyRes).collect(Collectors.toList());
        resSw.doubleQueue = new LinkedList<>();
        resSw.lIndex = -1;
        resSw.rIndex = -1;
        resSw.comparator = null;
        return resSw;
    }

    /**
     * 支持比较的器的构造方法
     *
     * @param sourceDate
     * @param comparator 比较器
     * @param <T>        无任何限制
     * @return SlideWindow 实例
     * @see #create(Collection)
     */
    public static <T> SlideWindow<T> create(Collection<T> sourceDate, Comparator<T> comparator) {
        SlideWindow<T> resSw = create(sourceDate);
        resSw.comparator = Objects.requireNonNull(comparator);
        return resSw;
    }

    /**
     * 检测左右边界的合法性
     * 左边界小于 有边界
     * 有边界小于sourceDataMemory的size
     *
     * @param lIndex 左边界
     * @param rIndex 有边界
     */
    private void checkLandR(int lIndex, int rIndex) {
        if (lIndex > rIndex) {
            throw new UnsupportedOperationException("滑动窗口左边界不能大于右边界");
        }
        if (rIndex >= sourceDataMemory.size()) {
            throw new UnsupportedOperationException("右边界不可向右");
        }
    }

    /***
     * 获取最极端的数据
     * 此数据的下标位于 doubleQueue 的头
     * @return T33 最极端的数据
     *          最大 or 最小 取决于 compareTo or 比较器compare的定义
     */
    private T getExtreme() {
        Integer doMoveMaxValueIndex = doubleQueue.peek();
        if (Objects.nonNull(doMoveMaxValueIndex)) {
            return sourceDataMemory.get(doubleQueue.peek());
        } else {
            return null;
        }
    }

    /***
     * 左边界向 右移动一步
     * 首先保证可以移动 左右边界关系不混乱
     * 然后如果左边界当前下标的数就是最极端的 那么 直接移动 删除第一个
     * 返回最极端的数据
     * @see #getExtreme()
     * @return T33 最极端的数据
     *          最大 or 最小 取决于 compareTo or 比较器compare的定义
     */
    public T lMoveOneStep() {
        checkLandR(lIndex + 1, rIndex);
        Integer nowMaxValueIndex = Objects.requireNonNull(doubleQueue.peek());
        if (nowMaxValueIndex == lIndex + 1) {
            lIndex++;
            doubleQueue.removeFirst();
        }
        return getExtreme();
    }
    /***
     * 右边界向 右移动一步
     * 首先保证可以移动 左右边界关系不混乱
     * 保持队列的单调性 从头到尾的值一直的单调减小的 ，so 头是最大的
     * （此处的大 小 可以理解为极端度，大小取决compareTo or 比较器compare的定义）
     * 如果当前期望加入的值 会破坏了这个单调性 那么会一直从队列移除，知道 可以保证单调性的加入
     * @see #getExtreme()
     * @return T33 最极端的数据
     *          最大 or 最小 取决于 compareTo or 比较器compare的定义
     */
    public T rMoveOnStep() {
        checkLandR(lIndex, rIndex + 1);
        rIndex++;
        T valueWaitInToQueue = sourceDataMemory.get(rIndex);
        if (doubleQueue.isEmpty()) {
            doubleQueue.addFirst(rIndex);
        } else {
            Integer minimumValueIndex = doubleQueue.getLast();
            T minimumValue = sourceDataMemory.get(minimumValueIndex);
            while (!isGreaterThan(minimumValue, valueWaitInToQueue) && !doubleQueue.isEmpty()) {
                minimumValueIndex = doubleQueue.removeFirst();
                minimumValue = sourceDataMemory.get(minimumValueIndex);
            }
            doubleQueue.addLast(rIndex);
        }
        return getExtreme();
    }

    /***
     * sourceValue 是否比  targetValue 更加极端
     * 优先使用比较器
     * 后强转为Comparable
     * 转换失败将抛出异常
     * @param sourceValue 原值
     * @param targetValue 目标值
     * @return 是否更加极端
     */
    private boolean isGreaterThan(T sourceValue, T targetValue) {
        if (Objects.nonNull(comparator)) {
            int compareRes = comparator.compare(sourceValue, targetValue);
            return compareRes > 0;
        } else {
            try {
                Comparable<T> sComparable = (Comparable<T>) sourceValue;
                return sComparable.compareTo(targetValue) > 0;
            } catch (Exception e) {
                throw new UnsupportedOperationException("请传入比较器，或可比较的对象");
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> integers = Arrays.asList(3, 2, 4, 6, 3, 7, 5, 3, 5);
        SlideWindow<Integer> slideWindow = create(integers);
        System.out.println(slideWindow.rMoveOnStep());
        System.out.println(slideWindow.rMoveOnStep());
        System.out.println(slideWindow.rMoveOnStep());
        int index = 3;
        System.out.println();
        while (index < integers.size()) {
            slideWindow.lMoveOneStep();
            System.out.println(slideWindow.rMoveOnStep());
//            index++;
        }
    }
}
